//
// Created by Administrator on 2022/7/8.
//
#include "Tree.cpp"
//先序遍历
//递归
void preorder(Tree root){
    if(root!=NULL){
        //访问根节点
        visit(root->data);
        //先序递归访问左子树
        preorder(root->leftChild);
        //先序递归访问右子树
        preorder(root->rightChild);
    }
}
//非递归
stack<TreeNode *> s;
void preordeR(Tree root){
    s.push(root);
    while(!s.empty()){
        TreeNode *p=s.top();
        visit(p->data);
        s.pop();
        if(p->rightChild!=NULL){
            s.push(p->rightChild);
        }
        if(p->leftChild!=NULL){
            s.push(p->leftChild);
        }
    }
}



//中序遍历
//递归
void inorder(Tree root){
    if(root!=NULL){
        //递归中序遍历左子树
        inorder(root->leftChild);
        //访问根节点
        visit(root->data);
        //递归中序遍历右子树
        inorder(root->rightChild);
    }
}
//非递归
stack <TreeNode *> s1;
void inordeR(Tree root){
    TreeNode *p=root;
    while(p!=NULL||!s1.empty()){
        //只要跟节点不为空且栈不为空重复访问左孩子并将节点压入栈中
        if(p!=NULL){
            s1.push(p);
            p=p->leftChild;
        }else{
            //当左孩子为空时，根指针退栈，访问根节点，遍历右子树
            TreeNode *p1=s1.top();
            visit(p1->data);
            s1.pop();
            p=p1->rightChild;
        }
    }
}
//后序遍历
//递归
void postorder(Tree root){
    if(root!=NULL){
        //后序递归访问左子树
        postorder(root->leftChild);
        //后序递归访问右子树
        postorder(root->rightChild);
        //访问根结点
        visit(root->data);
    }
}
//非递归
stack<TreeNode *> s2;
void postordeR(Tree root){
    TreeNode *p=root;
    TreeNode *q=NULL;
    while(p!=NULL||!s2.empty()){
        //遍历左子树
        if(p!=NULL){
            s2.push(p);
            p=p->leftChild;
        }else{
            TreeNode *m=s2.top();
            //无右孩子，或者右孩子已经被遍历过
            if(m->rightChild==NULL||m->rightChild==q){
                //访问根结点
                visit(m->data);
                //保存到q，代表已经访问过
                q=m;
                s2.pop();
                p=NULL;
            }else{
                p=m->rightChild;
            }
        }
    }
}
int main(){
    Tree tree = CreateTreeByFile("bianli.txt");
    preorder(tree);
    preordeR(tree);
    inorder(tree);
    inordeR(tree);
    postorder(tree);
    postordeR(tree);
}